import java.util.Arrays;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertArrayEquals;

/**
 *  * 这是 LeetCode 第 80 题 "删除有序数组中的重复项 II" 的解决方案
 *  https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii
 */
class RemoveDuplicatesFromSortedArrayII {
    /**
     * 方法：removeDuplicates
     *
     * 功能：从已排序数组中删除重复项，使得每个元素最多出现两次，并返回新数组的长度。原数组的前 k 个元素应为最终结果，其中 k 是返回的长度。
     *
     * 实现逻辑：
     * 1. 首先检查数组长度是否为 0，如果是，则直接返回 0。
     * 2. 初始化指针 `i` 为 2，表示前两个元素可以保留。
     * 3. 使用指针 `j` 从索引 2 开始遍历数组。
     * 4. 对于每个元素 `nums[j]`，检查它是否与 `nums[i-2]` 相同：
     *    - 如果不同，则将 `nums[j]` 赋值给 `nums[i]`，并将 `i` 增加 1。
     *    - 如果相同，则跳过该元素。
     * 5. 最后返回 `i`，即新数组的长度。
     *
     * 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要一次遍历数组。
     * 空间复杂度：O(1)，只使用了常数级的额外空间。
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len < 3){
            return len;
        }
        int i = 2;
        for(int j = 2; j < len; j++){
            if(nums[j] != nums[i-2]){
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }

    /**
     * 测试方法：用于验证 removeDuplicates 方法的正确性
     */
    public void testRemoveDuplicates() {
        RemoveDuplicatesFromSortedArrayII solution = new RemoveDuplicatesFromSortedArrayII();

        // 测试用例1：常规数组，包含重复元素超过两次
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        int result1 = solution.removeDuplicates(nums1);
        assertEquals(5, result1);
        assertArrayEquals(new int[]{1, 1, 2, 2, 3}, Arrays.copyOfRange(nums1, 0, result1));
        System.out.println("Test Case 1:");
        System.out.println("Expected: [1, 1, 2, 2, 3], length = 5");
        System.out.println("Actual: " + Arrays.toString(Arrays.copyOfRange(nums1, 0, result1)) + 
                         ", length = " + result1);

        // 测试用例2：空数组
        int[] nums2 = {};
        int result2 = solution.removeDuplicates(nums2);
        assertEquals(0, result2);
        System.out.println("\nTest Case 2:");
        System.out.println("Expected: [], length = 0");
        System.out.println("Actual: " + Arrays.toString(nums2) + ", length = " + result2);

        // 测试用例3：所有元素都相同
        int[] nums3 = {1, 1, 1, 1, 1};
        int result3 = solution.removeDuplicates(nums3);
        assertEquals(2, result3);
        assertArrayEquals(new int[]{1, 1}, Arrays.copyOfRange(nums3, 0, result3));
        System.out.println("\nTest Case 3:");
        System.out.println("Expected: [1, 1], length = 2");
        System.out.println("Actual: " + Arrays.toString(Arrays.copyOfRange(nums3, 0, result3)) + 
                         ", length = " + result3);

        // 测试用例4：已经符合条件的数组
        int[] nums4 = {1, 1, 2, 2, 3};
        int result4 = solution.removeDuplicates(nums4);
        assertEquals(5, result4);
        assertArrayEquals(new int[]{1, 1, 2, 2, 3}, Arrays.copyOfRange(nums4, 0, result4));
        System.out.println("\nTest Case 4:");
        System.out.println("Expected: [1, 1, 2, 2, 3], length = 5");
        System.out.println("Actual: " + Arrays.toString(Arrays.copyOfRange(nums4, 0, result4)) + 
                         ", length = " + result4);
    }

    public static void main(String[] args) {
        RemoveDuplicatesFromSortedArrayII solution = new RemoveDuplicatesFromSortedArrayII();
        try {
            solution.testRemoveDuplicates();
            System.out.println("\nAll test cases passed successfully!");
        } catch (AssertionError e) {
            System.out.println("\nTest failed: " + e.getMessage());
        }
    }
}